#define  _CRT_SECURE_NO_WARNINGS

#include <cstdlib>
#include <cstdio>
#include <ctime>

#include <string>
#include <vector>
#include <memory>

#include <boost/shared_ptr.hpp>
#include <boost/scoped_ptr.hpp>

#include <omp.h>

#include "TinyXML/tinyxml.h"

int     COMPUTERS_COUNT;
int     COMPUTER_ID;
int     PROGRAM_MAX_T_BYTES;
int     PROGRAM_MAX_A_BYTES;
int     PROGRAM_MAX_B_BYTES;
int     PROGRAM_MAX_C_BYTES;
int     PROGRAM_MAX_D_BYTES;
int     SIMULATION_TRESHOLD;

#define PROGRAM_COMMAND_L 0
#define PROGRAM_COMMAND_R 1
#define PROGRAM_COMMAND_S 2
#define PROGRAM_COMMAND_X 3

#define HERBERT_GRID_WALL           '#'
#define HERBERT_GRID_SPACE          '.'
#define HERBERT_GRID_WHITE_BUTTON   'o'
#define HERBERT_GRID_BLACK_BUTTON   'x'

class CHerbertLevel
{

public:

    CHerbertLevel(const char * id, const char * input, const char * output) : levelTag(id), levelOutput(output)
    {
        Initialize(); LoadLevel(input); BuildStateMachine();
    }

    bool Solved()
    {
        return score >= points;
    }

    int StartPosition()
    {
        return startPosition;
    }

    int * StateMachine()
    {
        return stateMachine;
    }

    int * Buttons()
    {
        return buttons;
    }

    void Update(int nButtons, char * A, int ASize, char * B, int BSize, char * C, int CSize, char * D, int DSize)
    {
        int currentScore = 0, currentBytes = 4 + ASize + BSize + CSize + DSize;

        if (nButtons == totalWhiteButtons) 
        {
            currentScore = (points * maxsize) / currentBytes;
        }
        else
        {
            int pointsPerButton = points / (2 * totalWhiteButtons);
            currentScore = nButtons * pointsPerButton;
        }

        if (score < currentScore)
        {
            #pragma omp critical
            {
                if (score < currentScore)
                {
                    int oldScore = score; score = currentScore;

                    char T[256]; _strtime(T); 
                    if (currentScore >= points) 
                    {
                        printf("%s | For level %s found PERFCT solution of %2d size. Score improved from %4d to %4d\n", T, levelTag.c_str(), currentBytes, oldScore, currentScore);
                    }
                    else
                    {
                        printf("%s | For level %s found better solution of %2d size. Score improved from %4d to %4d\n", T, levelTag.c_str(), currentBytes, oldScore, currentScore);
                    }

                    FILE * f = fopen(levelOutput.c_str(), "w");

                    fprintf(f, "%d\np(X):", currentScore);

                    for (int i = 0; i < ASize; i++)
                    {
                        if (A[i] == PROGRAM_COMMAND_L) fprintf(f, "l");
                        if (A[i] == PROGRAM_COMMAND_R) fprintf(f, "r");
                        if (A[i] == PROGRAM_COMMAND_S) fprintf(f, "s");
                        if (A[i] == PROGRAM_COMMAND_X) fprintf(f, "X");
                    }

                    fprintf(f, "p(");

                    for (int i = 0; i < BSize; i++)
                    {
                        if (B[i] == PROGRAM_COMMAND_L) fprintf(f, "l");
                        if (B[i] == PROGRAM_COMMAND_R) fprintf(f, "r");
                        if (B[i] == PROGRAM_COMMAND_S) fprintf(f, "s");
                        if (B[i] == PROGRAM_COMMAND_X) fprintf(f, "X");
                    }

                    fprintf(f, ")	(%d bytes)\n", currentBytes);

                    for (int i = 0; i < DSize; i++)
                    {
                        if (D[i] == PROGRAM_COMMAND_L) fprintf(f, "l");
                        if (D[i] == PROGRAM_COMMAND_R) fprintf(f, "r");
                        if (D[i] == PROGRAM_COMMAND_S) fprintf(f, "s");
                        if (D[i] == PROGRAM_COMMAND_X) fprintf(f, "X");
                    }

                    fprintf(f, "p(");

                    for (int i = 0; i < CSize; i++)
                    {
                        if (C[i] == PROGRAM_COMMAND_L) fprintf(f, "l");
                        if (C[i] == PROGRAM_COMMAND_R) fprintf(f, "r");
                        if (C[i] == PROGRAM_COMMAND_S) fprintf(f, "s");
                        if (C[i] == PROGRAM_COMMAND_X) fprintf(f, "X");
                    }

                    fprintf(f, ")\n\n");

                    for (int j = 1; j <= 25; j++)
                    {
                        for (int i = 1; i <= 25; i++) fprintf(f, "%c", grid[i][j]);
                        fprintf(f, "\n");
                    }
                    
                    fclose(f);
                }
            }
        }
    }

private:

    void Initialize()
    {
        totalWhiteButtons = 0; score = 0;
        for (int j = 0; j <= 26; j++)
        {
            for (int i = 0; i <= 26; i++) 
            {
                grid[i][j] = HERBERT_GRID_WALL;
            }
        }
    }

    void LoadLevel(const char * filename)
    {
        FILE * f = fopen(filename, "r");
        for (int j = 1; j <= 25; j++)
        {
            for (int i = 1; i <= 25; i++) 
            {
                char c; fscanf(f, "%c", &c);
                switch (c)
                {
                    case 'u' : grid[i][j] = HERBERT_GRID_SPACE; startPosition = (j * 27 + i) * 16; break;
                    case 'o' : grid[i][j] = HERBERT_GRID_WHITE_BUTTON; totalWhiteButtons++; break;
                    case '*' : grid[i][j] = HERBERT_GRID_BLACK_BUTTON; break;
                    case '.' : grid[i][j] = HERBERT_GRID_SPACE; break;
                    default  : grid[i][j] = HERBERT_GRID_WALL; break;
                }
            }
            fscanf(f, "\n");
        }
        fscanf(f, "points %d\nmaxsize %d\n", &points, &maxsize);
        fclose(f);
    }

    static void DecodeState(const int & s, int & x, int & y, int & dx, int & dy)
    {
        int p = s / 16; x = p % 27; y = p / 27;
        switch (s % 16)
        {
            case  0 : dx = +0; dy = -1; break;
            case  4 : dx = +1; dy = +0; break;
            case  8 : dx = +0; dy = +1; break;
            case 12 : dx = -1; dy = +0; break;
        }
    }

    static void EncodeState(int & s, const int & x, const int & y, const int & dx, const int & dy)
    {
        if (dx == +0 && dy == -1) s = (y * 27 + x) * 16 + 0;
        if (dx == +1 && dy == +0) s = (y * 27 + x) * 16 + 4;
        if (dx == +0 && dy == +1) s = (y * 27 + x) * 16 + 8;
        if (dx == -1 && dy == +0) s = (y * 27 + x) * 16 + 12;
    }

    void BuildStateMachine()
    {
        for (int y = 1; y <= 25; y++)
        {
            for (int x = 1; x <= 25; x++) 
            {
                buttons[y * 27 + x] = 0;
                if (grid[x][y] == HERBERT_GRID_BLACK_BUTTON) buttons[y * 27 + x] = +1;
                if (grid[x][y] == HERBERT_GRID_WHITE_BUTTON) buttons[y * 27 + x] = -1;
            }
        }
        for (int y = 1; y <= 25; y++)
        {
            for (int x = 1; x <= 25; x++) 
            {
                for (int p = 0; p < 16; p += 4)
                {
                    int state = (y * 27 + x) * 16 + p;

                    stateMachine[state + PROGRAM_COMMAND_L] = (y * 27 + x) * 16 + (p + 12) % 16;
                    stateMachine[state + PROGRAM_COMMAND_R] = (y * 27 + x) * 16 + (p +  4) % 16;
                    stateMachine[state + PROGRAM_COMMAND_S] = (y * 27 + x) * 16 +  p;

                    int dx, dy; DecodeState(state, x, y, dx, dy);

                    if (grid[x + dx][y + dy] != HERBERT_GRID_WALL)
                    {
                        int newstate, nx = x + dx, ny = y + dy; EncodeState(newstate, nx, ny, dx, dy); stateMachine[state + PROGRAM_COMMAND_S] = newstate;
                    }
                }
            }
        }
    }

    int             totalWhiteButtons;
    int             startPosition;

    int             score;
    int             points;
    int             maxsize;

    int             stateMachine[27 * 27 * 16];
    int             buttons[27 * 27];

    char            grid[27][27];
    std::string     levelTag;
    std::string     levelOutput;
};

std::vector<boost::shared_ptr<CHerbertLevel> > herbertLevels;

class CWorkingThread
{

public:

    CWorkingThread() : ProgramID(0), LocalProgramID(0), ASize(0), BSize(0), CSize(0), DSize(0)
    {

    }

    void GeneratePrograms(int threadID, int threadsCount)
    {
        THREAD_ID = threadID; THREADS_COUNT = threadsCount;
        for (int maxbytes = 3; maxbytes <= PROGRAM_MAX_T_BYTES - 4; maxbytes++)
        {
            #pragma omp barrier

            #pragma omp master
            {
                char T[256]; _strtime(T);
                printf("-------------------------------------------------------------------------------------------------\n%s | Testing %2d byte programs.\n", T, maxbytes + 4);
            }
            if (maxbytes <= PROGRAM_MAX_A_BYTES + PROGRAM_MAX_B_BYTES + PROGRAM_MAX_C_BYTES)
            {
                DSize = 0; RecursiveGenerateParamC(0, false, maxbytes);
            }
            if (PROGRAM_MAX_D_BYTES && maxbytes > 3 && (maxbytes - 1 <= PROGRAM_MAX_A_BYTES + PROGRAM_MAX_B_BYTES + PROGRAM_MAX_C_BYTES))
            {
                DSize = 1;
                D[0] = PROGRAM_COMMAND_L; RecursiveGenerateParamC(0, false, maxbytes - 1);
                D[0] = PROGRAM_COMMAND_R; RecursiveGenerateParamC(0, false, maxbytes - 1);
                D[0] = PROGRAM_COMMAND_S; RecursiveGenerateParamC(0, false, maxbytes - 1);
            }
        }
        #pragma omp master
        {
            char T[256]; _strtime(T);
            printf("%s | Done!\n", T);
        }
    }

private:

    static inline int GeneratePathByMask(const char * mask, const int maskSize, const char * source, const int sourceSize, char * destination, int destinationSize)
    {
        for (int i = 0; i < maskSize; i++)    
        {
            if (mask[i] != PROGRAM_COMMAND_X)
            {
                char P = destination[destinationSize++] = mask[i];
                if (P <= PROGRAM_COMMAND_R)
                {
                    if (destinationSize < 2 || destination[destinationSize - 2] == PROGRAM_COMMAND_S)
                    {
                        continue;
                    }
                    if (destination[destinationSize - 2] == P)
                    {
                        if (destinationSize < 3 || destination[destinationSize - 3] == PROGRAM_COMMAND_S)
                        {
                            continue;
                        }                        
                        destination[destinationSize - 3] = P ^ 1;
                    }
                    destinationSize -= 2;
                }
                continue;
            }
            for (int j = 0; j < sourceSize; j++)
            {
                char P = destination[destinationSize++] = source[j];
                if (P <= PROGRAM_COMMAND_R)
                {
                    if (destinationSize < 2 || destination[destinationSize - 2] == PROGRAM_COMMAND_S)
                    {
                        continue;
                    }
                    if (destination[destinationSize - 2] == P)
                    {
                        if (destinationSize < 3 || destination[destinationSize - 3] == PROGRAM_COMMAND_S)
                        {
                            continue;
                        }                        
                        destination[destinationSize - 3] = P ^ 1;
                    }
                    destinationSize -= 2;
                }
            }
        }
        return destinationSize;
    }

    void GeneratePath()
    {
        TSize = DSize; for (int i = 0; i < DSize; i++) T[i] = D[i];
        XSize = CSize; for (int i = 0; i < CSize; i++) X[i] = C[i];
        while (true)
        {
            // (A, X) -> T; (B, X) -> Y;
            TSize = GeneratePathByMask(A, ASize, X, XSize, T, TSize); if (TSize >= SIMULATION_TRESHOLD) break;
            YSize = GeneratePathByMask(B, BSize, X, XSize, Y, 0);

            // (A, Y) -> T; (B, Y) -> X;
            TSize = GeneratePathByMask(A, ASize, Y, YSize, T, TSize); if (TSize >= SIMULATION_TRESHOLD) break;
            XSize = GeneratePathByMask(B, BSize, Y, YSize, X, 0);
        }
    }

    void Simulate()
    {
        GeneratePath();
        for (int i = 0; i < (int)herbertLevels.size(); i++)
        {
            CHerbertLevel * pLevel = herbertLevels[i].get();
            if (!pLevel->Solved())
            {
                memset(tag, 0, 27 * 27 * sizeof(int));

                int   state        = pLevel->StartPosition();
                int * buttons      = pLevel->Buttons();
                int * stateMachine = pLevel->StateMachine();

                int id = 1, maxCount = 0, count = 0, pos = state >> 4;
                for (int k = 0; k < TSize; k++)
                {
                    state = stateMachine[state + T[k]]; int p = state >> 4;
                    if (pos != p)
                    {
                        pos = p; 
                        if (buttons[pos] != 0)
                        {
                            if (buttons[pos] > 0)
                            {
                                if (count > maxCount) maxCount = count; count = 0; id++;
                            }
                            else
                            {
                                if (tag[pos] != id)
                                {
                                    tag[pos] = id; count++;
                                }
                            }
                        }
                    }
                }
                if (count > maxCount) maxCount = count;
                pLevel->Update(maxCount, A, ASize, B, BSize, C, CSize, D, DSize);
            }
        }
    }

    void RecursiveGenerateParamA(int pos, bool flagS, bool flagX, int bytes)
    {
        if (bytes == 0 && flagS && flagX)
        {
            ProgramID++;
            if (ProgramID % COMPUTERS_COUNT == COMPUTER_ID)
            {
                LocalProgramID++;
                if (LocalProgramID % THREADS_COUNT == THREAD_ID)
                {
                    ASize = pos; Simulate();
                }
            }
        }
        if (bytes > 0) 
        {
            A[pos] = PROGRAM_COMMAND_X; RecursiveGenerateParamA(pos + 1, flagS, true, bytes - 1);
            A[pos] = PROGRAM_COMMAND_S; RecursiveGenerateParamA(pos + 1, true, flagX, bytes - 1);
            if (pos == 0 || A[pos - 1] >= PROGRAM_COMMAND_S)
            {
                A[pos] = PROGRAM_COMMAND_R; RecursiveGenerateParamA(pos + 1, flagS, flagX, bytes - 1);
            }
            if (pos == 0 || A[pos - 1] != PROGRAM_COMMAND_R)
            {
                if (pos < 2 || A[pos - 1] != PROGRAM_COMMAND_L || A[pos - 2] != PROGRAM_COMMAND_L)
                {
                    A[pos] = PROGRAM_COMMAND_L; RecursiveGenerateParamA(pos + 1, flagS, flagX, bytes - 1);
                }
            }
        }
    }

    void RecursiveGenerateParamB(int pos, bool flagS, bool flagX, int bytes)
    {
        if (bytes <= PROGRAM_MAX_A_BYTES && pos >= 2 && flagX)
        {
            BSize = pos; RecursiveGenerateParamA(0, flagS, false, bytes);
        }
        if (bytes > 1 && pos < PROGRAM_MAX_B_BYTES) 
        {
            B[pos] = PROGRAM_COMMAND_X; RecursiveGenerateParamB(pos + 1, flagS, true, bytes - 1);
            B[pos] = PROGRAM_COMMAND_S; RecursiveGenerateParamB(pos + 1, true, flagX, bytes - 1);
            if (pos == 0 || B[pos - 1] >= PROGRAM_COMMAND_S)
            {
                B[pos] = PROGRAM_COMMAND_R; RecursiveGenerateParamB(pos + 1, flagS, flagX, bytes - 1);
            }
            if (pos == 0 || B[pos - 1] != PROGRAM_COMMAND_R)
            {
                if (pos < 2 || B[pos - 1] != PROGRAM_COMMAND_L || B[pos - 2] != PROGRAM_COMMAND_L)
                {
                    B[pos] = PROGRAM_COMMAND_L; RecursiveGenerateParamB(pos + 1, flagS, flagX, bytes - 1);
                }
            }
        }
    }

    void RecursiveGenerateParamC(int pos, bool flagS, int bytes)
    {
        if (bytes <= PROGRAM_MAX_A_BYTES + PROGRAM_MAX_B_BYTES)
        {
            CSize = pos; RecursiveGenerateParamB(0, flagS, false, bytes);
        }
        if (bytes > 3 && pos < PROGRAM_MAX_C_BYTES) 
        {
            C[pos] = PROGRAM_COMMAND_S; RecursiveGenerateParamC(pos + 1, true, bytes - 1);
            if (pos == 0 || C[pos - 1] == PROGRAM_COMMAND_S)
            {
                C[pos] = PROGRAM_COMMAND_R; RecursiveGenerateParamC(pos + 1, flagS, bytes - 1);
            }
            if (pos == 0 || C[pos - 1] != PROGRAM_COMMAND_R)
            {
                if (pos < 2 || C[pos - 1] != PROGRAM_COMMAND_L || C[pos - 2] != PROGRAM_COMMAND_L)
                {
                    C[pos] = PROGRAM_COMMAND_L; RecursiveGenerateParamC(pos + 1, flagS, bytes - 1);
                }
            }
        }
    }

    long ProgramID, LocalProgramID;

    int THREADS_COUNT;
    int THREAD_ID;

    int tag[27 * 27];

    char A[256]; int ASize;
    char B[256]; int BSize;
    char C[256]; int CSize;
    char D[256]; int DSize;

    char T[1000000]; int TSize;
    char X[1000000]; int XSize;
    char Y[1000000]; int YSize;
};

void ReadConfigFile()
{
    TiXmlDocument config("mpHerbert.cfg");
    if (config.LoadFile())
    {
        TiXmlElement * pRoot = config.FirstChildElement();
        if (pRoot)
        {
            TiXmlElement * pSettings = pRoot->FirstChildElement("Settings");
            if (pSettings)
            {
                TiXmlElement * pCluster = pSettings->FirstChildElement("Cluster");
                if (pCluster)
                {
                    pCluster->Attribute("ComputersCount", &COMPUTERS_COUNT);
                    pCluster->Attribute("ComputerID", &COMPUTER_ID);
                }

                TiXmlElement * pGenerator = pSettings->FirstChildElement("Generator");
                if (pGenerator)
                {
                    pGenerator->Attribute("MaxProgramSize", &PROGRAM_MAX_T_BYTES);
                    pGenerator->Attribute("MaxParamASize", &PROGRAM_MAX_A_BYTES);
                    pGenerator->Attribute("MaxParamBSize", &PROGRAM_MAX_B_BYTES);
                    pGenerator->Attribute("MaxParamCSize", &PROGRAM_MAX_C_BYTES);
                    pGenerator->Attribute("MaxParamDSize", &PROGRAM_MAX_D_BYTES);
                }

                TiXmlElement * pSimulator = pSettings->FirstChildElement("Simulator");
                if (pSimulator)
                {
                    pSimulator->Attribute("MaximumDepth", &SIMULATION_TRESHOLD);
                }
            }
            TiXmlElement * pLevels = pRoot->FirstChildElement("Levels");
            if (pLevels)
            {
                TiXmlElement * pLevel = pLevels->FirstChildElement("Level");
                while (pLevel != NULL)
                {
                    herbertLevels.push_back(boost::shared_ptr<CHerbertLevel>(new CHerbertLevel(pLevel->Attribute("Tag"), pLevel->Attribute("Input"), pLevel->Attribute("Output"))));
                    pLevel = pLevel->NextSiblingElement("Level");
                }
            }
        }
    }
    else
    {
        printf("Failed to load config file.\n");
        exit(1);
    }
}

int main(int argc, char * argv[])
{
    ReadConfigFile(); 

    #pragma omp parallel
    {
        boost::scoped_ptr<CWorkingThread> thread(new CWorkingThread());
        thread->GeneratePrograms(omp_get_thread_num(), omp_get_num_threads());
    }

    return 0;
}
